(Available with SDK v2.0.3)

The Gameboard SDK has Navigation building that allows you to quickly build a navigable graph to find the shortest path or determine the cost of a move. The Gameboard Navigation Graph includes 3 important concepts:

• Waypoints: Locations GB-NavAgents piece can go to
• Edges: Connections between waypoints. This includes a cost for traversing.
• GB-NavAgent: Agent trying to move through the Navigation Graph

With these items, you can build a traversable graph and control your agent through the graph based on the cost of each movement or find the shortest possible path to a particular waypoint.

NOTE: We use the A* path searching algorithm to calculate the shortest possible path.

To use the navigation tools, you first want to create a Navigation Graph that shows the possible waypoints the GB-NavAgent can occupy.

To start creating the navigation graph, go to the Gameboard > Navigation > Add Waypoint Graph

This graph will be the basis of all of your navigation.

You first need to decide if you graph will be directed or undirected.

• Directed: Edges have a direction, meaning you could potentially go one direction and not go back. For example, you could jump down a ledge and not be able to climb back up it. You would also want to use a directed graph if the cost of movement could be different depending on which way the GB-NavAgent is moving. Like it costs 3 to climb a ledge, but only 1 to jump down that same ledge.
• Undirected: Edges go both ways and cost the same both ways. Use this type of graph if you the GB-NavAgent can travel both directs and the cost of moving between waypoints will be consistent, no matter if they are moving to or from that space.

NOTE: If change the Graph Type at any point, make sure to click the Rebuild Adjacency Matrix button to rebuild the edges/nodes properly.

Waypoints

Waypoints make up the locations that you want the GB-NavAgent to be able to travel to.

Create

You can create new waypoints by clicking the Add Waypoint Node button on the Waypoint Graph.

Modify

• Upon creating the waypoint node, move it to the correct location within your scene.
• You can also add an Annotation to the node that can be used for things like the GB-NavAgent's IsValidWaypointEvaluator to check is an waypoint is a valid location for a specific GB-NavAgent. (e.g. the GB-NavAgent can't swim, and the Annotation is set to water, the IsValidWaypointEvaluator for that GB-NavAgent would return false. See Create Agent section for a more detailed example)

Waypoints are also aware of the GB-NavAgents that are currently at their location. To get those GB-NavAgents, call GetNavAgents() on the waypoint.

List<GbWaypointGB-NavAgent> GB-NavAgentsAtWaypoint = currentWaypoint.GetGB-NavAgents();

Edges

Now that you have all the waypoints that a GB-NavAgent can get to created in your scene, you need to connect those waypoints based on valid methods of movement with edges.

Create

• Select two waypoints that you want to connect.
  • If it is a directional graph, make sure to select the nodes in the order you want the direction to go. (If you want the edge to connect 1 -> 2, first select 1 and then 2 in a directional graph)
• Click the Create Edge button that appears upon selection or select Gameboard > Navigation > Edit Graph > Add Waypoint Edge

Modify

Upon creating the edge, you will see some Edge options appear in the GbWaypoint inspector.

• Edge Cost: The cost it takes to travel this edge, this will be used when determining the shortest path
• Edge Annotation: A descriptor that can be used to distinguish the edge when determining factor for the GB-NavAgent (e.g. The GB-NavAgent can fly, so any edges annotated with cliff-edge that previously cost more would be reduced for this particular agent)

You can also destroy the edge by clicking the Destroy Edge button if you no longer want it to be a viable path for the Nav Agent.

Now that you have built out a Navigation Graph with Waypoints and Edges, you just need a GB-NavAgent to traverse the graph. The GB-NavAgent** requires a Rigidbody and Collider** for the triggers of the Navigation Graph.

To create a GB-NavAgent, create a GameObject and select it, then click Gameboard > Navigation > Add GB-NavAgent

This will add a Rigidbody and Sphere Collider if some rigibody and Collider isn't already found on the GameObject, and it will add the GB Waypoint Nav Agent script.

• Level Graph: This should be the Navigation Graph you just created.
• Stat: This is the waypoint you expect this GB-NavAgent to start at.
• End: This is the waypoint the GB-NavAgent is trying to get to.

From here, you would want to create your own Script to add to yout GB-NavAgent to respond to the Navigation Graph and Waypoints as you would like.

First, you will want to get a reference to the GB-NavAgent to make it available through out our script.

    GbWaypointNavAgent mNavAgent;

Then we want to get a reference to that GB-NavAgent script, along with start listening to events from the NavAgent.

    void Start()
    {
        mNavAgent = GetComponent<GbWaypointNavAgent>();

        // Register to know when the agent enters a waypoint.
        mNavAgent.OnWaypointEntered += OnWaypointEnteredReceiver;

        // Register to know when the agent exits a waypoint.
        mNavAgent.OnWaypointExited += OnWaypointExitedReceiver;

        // Register to know when the pathfinder is complete. Usuful if the search is handed off to a task.
        mNavAgent.OnPathFindingComplete += OnShortestPathSearchComplete;

        // Register to know when the pathfinder is done looking for paths of at most X cost.
        mNavAgent.OnPathOptionsSearchComplete += OnPathsOfAtMostCostComplete;

        // Register to return if a waypoint is valid for this particular agent
        mNavAgent.IsValidWaypointEvaluator += IsValidWaypoint;

        //Register to return if an edge is allowed to be traversed by the agent
        mNavAgent.IsValidWaypointPathEvaluator += IsValidWaypointPath;

        //Register to override the cost of an edge based on the agent
        mNavAgent.GetCostToWaypointEvaluator += GetCostToWaypoint;
    }

Path Finding

You can get the possible paths for an agent by using FindPath or FindPathsOfAtMostCost on the GB-NavAgent.

You can also offload the FindPath or FindPathsOfAtMostCost to a background Task, they will invoke the OnPathFindingComplete and OnPathOptionsSearchComplete

You can listen to when an agent is entering or exiting a waypoint. This may be useful if you are doing something like highlighting the possible paths for the agent as they move.

Let's use this method that highlights a path.

private List<GbGraphEdge> mPrevPath;
private void SetPathHighlight(List<GbGraphEdge> path)
{
    // Remove previous highlight
    SetPathHighlightHelper(mPrevPath, false);
    //Highlight new path
    SetPathHighlightHelper(path, true);
    //Keep track of current highlight
    mPrevPath = path;
}

private void SetPathHighlightHelper(List<GbGraphEdge> path, highlight)
{
    foreach (GbGraphEdge edge in path)
    {
        if (edge.sourceNode != null)
        {
            edge.sourceNode.ToggleHighlight(highlight);
        }

        if (edge.targetNode != null)
        {
            edge.targetNode.ToggleHighlight(highlight);
        }
    }
}

And when an agent enters a waypoint, we can highlight the shortest path to the agent's end waypoint

void OnWaypointEnteredReceiver(GbWaypoint waypoint)
{
    List<GbGraphEdge> pathFound = mNavAgent.FindPath(mNavAgent.end);
    SetPathHighlight(pathFound, true);
}

or

void OnWaypointEnteredReceiver(GbWaypoint waypoint)
{
    Task.Run(() => mNavAgent.FindPath(mNavAgent.end));
}

void OnShortestPathSearchComplete(List<GbGraphEdge> path)
{
    SetPathHighlight(path, true);
}

FindPath will return the shortest paths available from the agent to the specified waypoint. FindPathsOfAtMostCost will return all possible paths within the given cost. You can then see all the possible paths available, or query for the cost to go to particular waypoints.

void OnPathsOfAtMostCostComplete(GbPathOptions paths)
{
    // Returns a list of paths (edges)
    var paths = paths.GetPathOptions();

    //Returns the lowest cost to get to a particular waypoint.
    var cost = paths.GetLowestCostForNode(mNavAgent.end);
}

Modifying Possible Path/Cost

You may want to modify what is possible for a particular agent based on the environment they are going through. You can do that with the evaluator events and modifying what is valid or the cost of going particualr paths based on annotations of the edges and waypoints.

   bool IsValidWaypoint(GbWaypoint node)
    {
        // Here you can check if this navigiator can go to the node
        // for example, if this navigator can't navigate water, return false if the annotation is 'water', and true otherwise.

        return node.annotation != "water";
    }

    bool IsValidWaypointPath(GbWaypoint current, GbWaypoint node)
    {
        // Here you can check if this navigiator can go from one node to another, potentially checking the edge's annotation
        // for example, if this agent can't fly, it wouldn't be able to navigate a cliff edge

        var edge = mNavAgent.levelGraph.GetWaypointEdge(current, node);

        return edge.annotation != "cliff-edge";
    }

    int GetCostToWaypoint(GbWaypoint current, GbWaypoint node)
    {
        // Here you can modify the cost to navigate an edge based on the agents abilities
        // for example, if this agent can't navigate the forest quickly, you can change it to cost more to traverse a "forest" edge.

        var edge = mNavAgent.levelGraph.GetWaypointEdge(current, node);

        return edge.annotation == "forest" ? edge.cost*2 : edge.cost;
    }

If you want your navigation paths to be grid/tile based, you can use the optional matrix to add on more functionality, like path building based on tiles that can be rotated within the grid.

To use the matrix, you will want a GB-Waypoint-Matrix wrapping a GB-Waypoint-Graph.

You can generate this by using the Gameboard Menu Gameboard > Navigation > Add Waypoiny Maytrix Grid

and that will generate this structure for you:

Generate the Grid

Now, if you inspect the GB-Waypoint-Matrix, you will see some options to help you set up your grid. Specifiy the number of rows and columns you could like, and then click Generate Grid to generate the proper matrix. You can also set the Wrap Paths flag, which if true means that the path can wrap from one side of the matrix grid to the other, like PacMan.

Create the Tile / Map Layer

Once you have the grid generated, you now will want to create your map/tile layer that will dictate the path. This will include GB Tiles that make up the grid, and you will need to specify the valid paths for those tile shapes.

Once you have your GameObjects representing the tiles, you can make them GB Tiles by selecting them and using the Gameboard > Navigation > Add GB-Tile menu option.

Now click into that GB Tile (Script) to specify the tile's shape or path by checking all the valid paths for that specific tile. Each checkbox indicates if the path off that tile are valid paths.

You can see which paths are specified by the colored Gizmo, but if you are having a hard time seeing the gizmo below the waypoints you can set the Gizmo Elavation so they are more prominently shown.

NOTE: The Tile Shape specification in the inspector assumes you have your Unity space is oriented so Z+ is forward and X+ is right. So North is Z+, South Z-, East is X+ and West is X- for the orientation of the tile paths.

Example of a 4 Way Tile Setup

Example of a 3 Way Tile Setup

By default, the tile paths will be considered valid regardless of the specified shape if they are adjacent. You can check if the path is valid based on the tile shape by using the PathsOverlap method on the GbTile object when checking if paths are valid, or you can set the Only Valid If Paths Overlap flag on the GB Waypoint Matrix. If this flag is true, the logic for verifying the path based on the tile shape will be done for you.

If you would manually like to do that logic, you can implement it yourself with the IsValidWaypointPathEvaluator event and leave the Only Valid If Paths Overlap flag set to false.

//This logic will be done automatically if Only Valid If Paths Overlap is true
bool IsValidWaypointPath(GbWaypoint sourceWaypoint, GbWaypoint targetWaypoint)
{
    // Paths are only valid for this agent if there is a path between the two tiles.
    Vector2Int sourceTileIndex = mGrid.GetWaypointIndex(sourceWaypoint.transform.position);
    Vector2Int targetTileIndex = mGrid.GetWaypointIndex(targetWaypoint.transform.position);

    // Find the source tile.
    GbTile sourceTile = mGrid.GetTileAt(sourceTileIndex);
    // Find the target tile.
    GbTile targetTile = mGrid.GetTileAt(targetTileIndex);

    // If either is null, it isn't a valid path
    if (sourceTile == null || targetTile == null) return false;

    // Check if there is an overlap in their shape.
    bool valid = sourceTile.PathsOverlap(targetTile);

    return valid;
}

Now that we have the grid set up, we can listen to when the Grid changes. This could be useful if you want to do something like trigger agents to calculate their path whenever the grid changes due to something like a tile rotation.

Lets say we have a car Gb-NavAgent and we want to know whenever the grid changed to recalculate the it's path. So first, let's get and keep track of the GbWaypointMatrix, and then listen to the OnGridChanged events.

    private GbWaypointMatrix mGrid;

    void Start()
    {
        mNavAgent = GetComponent<GbWaypointNavAgent>();
        mGrid = mNavAgent.GetOwnerMatrix();
        mGrid.OnGridChanged += OnGridChanged;
    }

Now we can find our nav agents path anytime the grid changes.

void OnGridChanged(GbWaypointMatrix grid, GbTile tile, int row, int col)
    {
        // Search for a new path when the grid changes.
        mNavAgent.FindPath(mNavAgent.end);
    }

To manipulate the tiles within the matrix and recalculate the path, you can use the buttons in the GB Tile Script, or call those methods directly on the GbTile object:

• Rotate Left - RotateClockwise(bool updateTransform, bool notifyChange)
• Rotate Right - RotateCounterClockwise(bool updateTransform, bool notifyChange)
• Set Tile - SetTile(bool notifyChange) - sets the tile into the grid, making the paths valid
• UnSet Tile - UnSetTile(bool notifyChange) - removes the tile from the grid, removing the paths

These methods will keep the tile within the grid and calculate the correct path based on the shape specified for the tile.

In this example, we can get a tile from the grid based on a position, and then manipulate that tile. In the last code example we got the owner matrix, now we want to find the tile at a specific position and manipulate it.

Vector2Int sourceTileIndex = mGrid.GetWaypointIndex(sourceWaypoint.transform.position);
GbTile sourceTile = mGrid.GetTileAt(sourceTileIndex);
//Now that we have the tile at the location, we can manipulate it

//These methods will either remove or place the tile within the matrix and notify of the change
sourceTile.SetTile(true);
sourceTile.UnSetTile(true);

//These methods will rotate the tiles, update the trasform, and notify of the change
sourceTile.RotateClockwise(true, true);
sourceTile.RotateCounterClockwise(true, true);

Although we are working in a managed environment it is always a good idea to clean the listeners when no longer needed.

    void OnDestroy()
    {
        mNavAgent.OnWaypointEntered -= OnWaypointEnteredReceiver;
        mNavAgent.OnWaypointExited -= OnWaypointExitedReceiver;
        mNavAgent.OnPathFindingComplete -= OnShortestPathSearchComplete;
        mNavAgent.OnPathOptionsSearchComplete -= OnPathsOfAtMostCostComplete;
        mNavAgent.IsValidWaypointEvaluator -= IsValidWaypoint;
        mNavAgent.GetCostToWaypointEvaluator -= GetCostToWaypoint;

        //If you used the optional Matrix, you will want to clean that up as well
        mGrid.OnGridChanged -= OnGridChanged;
    }

This section include the entire code in one single, easy to copy section.

    GbWaypointNavAgent mNavAgent;
    private List<GbGraphEdge> mPrevPath;

    //(OPTIONAL) If you are using the matrix
    private GbWaypointMatrix mGrid;

    // Start is called before the first frame update
    void Start()
    {
        mNavAgent = GetComponent<GbWaypointNavAgent>();
        //(OPTIONAL) If you are using the matrix
        mGrid = mNavAgent.GetOwnerMatrix();
        mGrid.OnGridChanged += OnGridChanged;

        // Register to know when the agent enters a waypoint.
        mNavAgent.OnWaypointEntered += OnWaypointEnteredReceiver;

        // Register to know when the agent exits a waypoint.
        mNavAgent.OnWaypointExited += OnWaypointExitedReceiver;

        // Register to know when the pathfinder is complete. Usuful if the search is handed off to a task.
        mNavAgent.OnPathFindingComplete += OnShortestPathSearchComplete;

        // Register to know when the pathfinder is done looking for paths of at most X cost.
        mNavAgent.OnPathOptionsSearchComplete += OnPathsOfAtMostCostComplete;

        // Register to return if a waypoint is valid for this particular agent
        mNavAgent.IsValidWaypointEvaluator += IsValidWaypoint;

        //Register to return if an edge is allowed to be traversed by the agent
        mNavAgent.IsValidWaypointPathEvaluator += IsValidWaypointPath;

        //Register to override the cost of an edge based on the agent
        mNavAgent.GetCostToWaypointEvaluator += GetCostToWaypoint;
    }

    void OnDestroy()
    {
        mNavAgent.OnWaypointEntered -= OnWaypointEnteredReceiver;
        mNavAgent.OnWaypointExited -= OnWaypointExitedReceiver;
        mNavAgent.OnPathFindingComplete -= OnShortestPathSearchComplete;
        mNavAgent.OnPathOptionsSearchComplete -= OnPathsOfAtMostCostComplete;
        mNavAgent.IsValidWaypointEvaluator -= IsValidWaypoint;
        mNavAgent.IsValidWaypointPathEvaluator -= IsValidWaypointPath;
        mNavAgent.GetCostToWaypointEvaluator -= GetCostToWaypoint;

        //If you used the optional Matrix, you will want to clean that up as well
        mGrid.OnGridChanged -= OnGridChanged;
    }

    void OnWaypointEnteredReceiver(GbWaypoint waypoint)
    {
        Task.Run(() => mNavAgent.FindPath(mNavAgent.end));
    }

    void OnWaypointExitedReceiver(GbWaypoint waypoint)
    {
        // Agent left waypoint
    }

    void OnShortestPathSearchComplete(List<GbGraphEdge> path)
    {
        SetPathHighlight(path);
    }

    void OnPathsOfAtMostCostComplete(GbPathOptions paths)
    {
        // Returns a list of paths (edges)
        var paths = paths.GetPathOptions();

        //Returns the lowest cost to get to a particular waypoint.
        var cost paths.GetLowestCostForNode(mNavAgent.end);
    }


    //(OPTIONAL) If you are using the matrix
    void OnGridChanged(GbWaypointMatrix grid, GbTile tile, int row, int col)
    {
        // Search for a new path when the grid changes.
        mNavAgent.FindPath(mNavAgent.end);
    }

    bool IsValidWaypoint(GbWaypoint node)
    {
        // Here you can check if this navigiator can go to the node
        // for example, if this navigator can't navigate water, return false if the annotation is 'water', and true otherwise.

        return node.annotation != "water";
    }

    bool IsValidWaypointPath(GbWaypoint current, GbWaypoint node)
    {
        // Here you can check if this navigiator can go from one node to another, potentially checking the edge's annotation
        // for example, if this agent can't fly, it wouldn't be able to navigate a cliff edge

        var edge = mNavAgent.levelGraph.GetWaypointEdge(current, node);

        return edge.annotation != "cliff-edge";

        //(OPTIONAL) If you are using the matrix and the Only Valid If Paths overlap flag is false,
        //you can check based on overlapping paths here and return valid accordingly

        Vector2Int sourceTileIndex = mGrid.GetWaypointIndex(sourceWaypoint.transform.position);
        Vector2Int targetTileIndex = mGrid.GetWaypointIndex(targetWaypoint.transform.position);

        // Find the source tile.
        GbTile sourceTile = mGrid.GetTileAt(sourceTileIndex);
        // Find the target tile.
        GbTile targetTile = mGrid.GetTileAt(targetTileIndex);

        // If either is null, it isn't a valid path
        if (sourceTile == null || targetTile == null) return false;

        // Check if there is an overlap in their shape.
        bool valid = sourceTile.PathsOverlap(targetTile); //use this with the return

        return valid;
    }

    int GetCostToWaypoint(GbWaypoint current, GbWaypoint node)
    {
        // Here you can modify the cost to navigate an edge based on the agents abilities
        // for example, if this agent can't navigate the forest quickly, you can change it to cost more to traverse a "forest" edge.

        var edge = mNavAgent.levelGraph.GetWaypointEdge(current, node);

        return edge.annotation == "forest" ? edge.cost*2 : edge.cost;
    }

    private void SetPathHighlight(List<GbGraphEdge> path)
    {
        // Remove previous highlight
        SetPathHighlightHelper(mPrevPath, false);
        //Highlight new path
        SetPathHighlightHelper(path, true);
        //Keep track of current highlight
        mPrevPath = path;
    }

    private void SetPathHighlightHelper(List<GbGraphEdge> path, bool highlight)
    {
        foreach (GbGraphEdge edge in path)
        {
            if (edge.sourceNode != null)
            {
                edge.sourceNode.ToggleHighlight(highlight);
            }

            if (edge.targetNode != null)
            {
                edge.targetNode.ToggleHighlight(highlight);
            }
        }
    }